package org.concepts.algorithm.datastructure;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * Linked list.
 * <p/>
 * 
 * It's not thread safe.
 * 
 * 
 * @author vvvv
 * 
 * @param <E>
 */
public class LinkedList<E> implements List<E> {

  private Item<E> head = null;
  private Item<E> tail = null;
  private int size = 0;

  /**
   * BigO analysis: The addition to the list is a constant time operation as we
   * only need to modify the pointer of the last element.
   * 
   * @see List#add(Object)
   * @return false is returned if data passed in is null.
   */
  public boolean add(E data) {
    if (data == null) {
      return false;
    }

    Item<E> item = new Item<E>();
    item.data = data;
    if (head == null) {
      head = item;
      tail = item;
    } else {
      tail.nextItem = item;
      tail = item;
    }
    size++;
    return true;
  }

  /**
   * Returns true if the list contains the specified data.
   * 
   * @param data
   *          data. can be null.
   * @return
   */
  public boolean contains(Object data) {
    if (containsItem(data) != null) {
      return true;
    }
    return false;
  }

  /**
   * Returns the item that contains the specified data. Null is returned if the
   * data is not found.
   * 
   * @param data
   * @return returns
   */
  private Item containsItem(Object data) {
    if (data == null || head == null) {
      return null;
    }

    Item<E> currItem = head;
    while (!currItem.data.equals(data)) {
      currItem = currItem.nextItem;
      if (currItem == null) {
        return null;
      }
    }
    return currItem;
  }

  private static class Item<E> {
    private Item<E> nextItem;
    private E data;
  }

  /**
   * @see List#add(int, Object)
   */
  @Override
  public void add(int index, E element) {
    if (element == null) {
      return;
    }
    validateIndex(index);

  }

  private void validateIndex(int index) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("Index " + index
          + " is out of bounds. List size " + size);
    }
  }

  /**
   * Returns the item before the specified index.
   * 
   * @param index
   * @return
   */
  private Item getBeforeIndex(int index) {
    if (index <= 0 || index > size) {
      throw new IndexOutOfBoundsException("index " + index
          + " is out of bounds");
    }
    
    Item currItem = head;
    
    
    for (int cnt = 2; cnt < index; cnt++) {
      currItem = currItem.nextItem;
    }
    return currItem;
    
  }

  @Override
  public boolean addAll(Collection<? extends E> c) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public boolean addAll(int index, Collection<? extends E> c) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public void clear() {
    // TODO Auto-generated method stub

  }

  @Override
  public boolean containsAll(Collection<?> c) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public E get(int index) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public int indexOf(Object o) {
    // TODO Auto-generated method stub
    return 0;
  }

  @Override
  public boolean isEmpty() {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public Iterator<E> iterator() {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public int lastIndexOf(Object o) {
    // TODO Auto-generated method stub
    return 0;
  }

  @Override
  public ListIterator<E> listIterator() {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public ListIterator<E> listIterator(int index) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public boolean remove(Object o) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public E remove(int index) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public boolean removeAll(Collection<?> c) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public boolean retainAll(Collection<?> c) {
    // TODO Auto-generated method stub
    return false;
  }

  @Override
  public E set(int index, E element) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public int size() {
    // TODO Auto-generated method stub
    return 0;
  }

  @Override
  public List<E> subList(int fromIndex, int toIndex) {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public Object[] toArray() {
    // TODO Auto-generated method stub
    return null;
  }

  @Override
  public <T> T[] toArray(T[] a) {
    // TODO Auto-generated method stub
    return null;
  }

}
